package cn.dlc.com.sort;

import java.util.Arrays;

/**
 * @author 邓立川
 * @date 2021/3/15 21:56
 * @desc 快速排序{6,1,2,7,9,3,4,5,8}
 */
public class Demo14 {

    public static void main(String[] args) {
        Integer[] arr = {6,1,2,7,9,3,4,5,8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 对数组进行排序
     * @param arr
     */
    private static void sort(Comparable[] arr) {
        // 定义最小和最大的索引
        int min = 0;
        int max = arr.length -1;

        // 分组
        sort(arr, min, max);
    }

    /**
     * 分组
     * @param arr
     * @param min
     * @param max
     */
    private static void sort(Comparable[] arr, int min, int max) {
        // 安全性校验
        if(min >=max) {
            return;
        }

        // 分组(返回值为分界所在的索引)
        int partition = partition(arr, min, max);

        // 左边组有序
        sort(arr,min,partition-1);

        // 右边也有序
        sort(arr,partition + 1,max);
    }

    /**
     * 切分
     * @param arr
     * @param min
     * @param max
     * @return
     */
    private static int partition(Comparable[] arr, int min, int max) {
        // 获取基准值
        Comparable key = arr[min];

        // 定义两个指针，分别指向最小索引处和最大索引的下一个位置（因为要移动）
        int left = min;
        int right = max + 1;

        // 切分
        while(true) {

            // 先往左边扫,找到小于基准值的，停止
            // 这里是先往前走一位，然后比较
            while(SortUtils.lesser(key , arr[--right])) {
                if(right == min) {
                    // 如果一直没找到，到起始位置也停止
                    break;
                }
            }
            // 接着往右边扫，找到大于基准值的，停下来
            while(SortUtils.lesser(arr[++left], key)) {
                if(left == max) {
                    // 一直没找到，到最后也停下来
                    break;
                }
            }

            // 上面两个循环结束之后，判断有没有完成整个数组的扫描
            // 如果扫描完毕，结束循环
            if(left >= right) {
                break;
            } else {
                // 如果没有扫描结束，交换值
                SortUtils.exchange(arr,left,right);
            }
        }

        // 循环完成，交换基准值(这里写right和left都行，因为指向同一个值)
        SortUtils.exchange(arr,min, right);

        // 返回哪个都行。
        return right;
    }
}
